package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//二叉搜索树转换成双向环形链表
//中序遍历的基础上:
//1、遍历到第一个节点时，赋值给head节点，除了当前节点也要存储pre节点，pre和cur相互指向
func Convert(root *TreeNode) *TreeNode {
	var dfs func(cur *TreeNode)
	var pre, head *TreeNode
	dfs = func(cur *TreeNode) {
		//到达叶子节点末尾返回
		if cur == nil {
			return
		}
		//中序遍历，遍历左节点，从小到大
		dfs(cur.Left)

		//将节点的右节点指向中序遍历的下一个节点，即指向较大的数
		//第一次给pre节点赋值时，此时递归到最左端，将最小节点赋值给head，pre赋值cur
		if pre != nil {
			pre.Right = cur
		} else {
			head = cur
		}

		//当前节点指向左端，即较小值
		cur.Left = pre

		//pre赋值为cur
		pre = cur

		//左节点遍历到头以后开始遍历右节点
		dfs(cur.Right)

	}
	//遍历二叉树修改为双向链表
	dfs(root)
	//将双向链表头尾相连
	pre.Right = head
	head.Left = pre
	return head
}

func main() {
	t := TreeNode{
		3,
		&TreeNode{2, &TreeNode{1, nil, nil}, nil},
		&TreeNode{4, nil, nil},
	}
	t1 := Convert(&t)
	count := 0
	for t1 != nil && count < 6 {
		fmt.Println(t1.Val)
		t1 = t1.Right
		count++
	}
}
